package com.sise.Sort;

/**
 *      33. 搜索旋转排序数组
 *
 *      整数数组 nums 按升序排列，数组中的值 互不相同 。
 *      在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，
 *      使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。
 *      例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为[4,5,6,7,0,1,2] 。
 *      给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1。
 *
 *      输入：nums = [4,5,6,7,0,1,2], target = 0
 *      输出：4
 *
 *      如果要查找的数值为 5，
 *
 *      题解：
 *          使用二分搜索 while。
 *          将数组一分为二，那么一定有一边是有序的，另一边可能是有序或者无序的（利用 num[mid]、num[start]、num[end] 判断大小即可，利用升序性质）
 *          对其有序区间进行二分查找（根据有序部分确定我们该如何改变二分查找的上下界）
 *          对其 无序区间再次进行一分为二，继续以上过程（因为必须将无序转变为有序，才可以使用二分查找法，进而确定索引位置）
 *
 *      以 [4,5,6,7,0,1,2], target = 1 为例子，一开始的有序部门为左边，但是在 左边的右区间查找此值，却寻找不到；
 *      故此将 left = mid + 1，对其右边的无序数组重复以上动作
 *
 */
public class _33_search {

    public int search(int[] nums, int target) {

        int length = nums.length;
        if (length == 0) return -1;
        int left = 0;
        int right = length - 1;

        while (left <= right) {                                             // 二分搜索使用的是 while 循环，而不是 递归
            int mid = left + (right - left) / 2;                            // 二分搜索的中间值
            if (nums[mid] == target) return mid;                            // 如果恰好等于目标值，那么就返回（返回最终值 的位置）

            if (nums[mid] < nums[right]) {                                  // 如果中间值小于最右值，那么说明右边有序
                if (target > nums[mid] && target <= nums[right]) {          // 上面只是确定了右边有序，此时还需要确定 target 在左区间 还是 右区间
                    left = mid + 1;                                         // 正常的二分搜索
                } else {
                    right = mid - 1;
                }
            } else {                                                        // else 说明左边有序
                if (target >= nums[left] && target < nums[mid]) {           // 判断 target 是否在左区间
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
}